package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class Q1020 {

    /**
     * @param graph: a 2D array
     * @return: all possible paths from node 0 to node N-1
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // Write your code here
    	List<List<Integer>> rs = new ArrayList<>();
    	if(graph == null) {
    		return rs;
    	}
    	int target = graph.length - 1;
    	List<Integer> tmp = new ArrayList<>();
    	bianli(0, graph, target, tmp, rs);
    	return rs;
    }

	private void bianli(int i, int[][] graph, int target, List<Integer> tmp, List<List<Integer>> rs) {
		List<Integer> tmp2 = new ArrayList<>(tmp);
		tmp2.add(i);
		if (i == target) {
			rs.add(tmp2);
			return;
		}
		int [] gs = graph[i];
		for(int j : gs) {
			bianli(j, graph, target, tmp2, rs);
		}
	}

	@Test
	public void testAllPathsSourceTarget() {
		int [][]graph = {{4,3,1},{3,2,4},{3},{4},{}};
		System.out.println(allPathsSourceTarget(graph));
	}
}
